package bishiqiangxun;
import java.util.*;
public class Test3 {
    //题目  : 笔试强训 day33  第三题  字符串的排列
    //算法 : dfs  /递归   +  剪枝
    //定义一下全局变量
    static boolean[] flg = new boolean[11];
    static StringBuffer str1 = new StringBuffer();  //路径
    static char[] cs;
    static int n;
    static ArrayList<String> list = new ArrayList<>();

    public ArrayList<String> Permutation (String str) {
        // write code here
        //dfs  + 剪枝
        n = str.length();
        cs = str.toCharArray();
        //排序
        Arrays.sort(cs);

        //开始dfs
        dfs(0);
        return list;
    }

    public static void dfs(int index) {
        if(index == n) {
            list.add(str1.toString());
            return;
        }


        for(int i = 0; i< n; i++) {
            //如果用过了 直接返回
            if(flg[i]) continue;
            if( i > 0 &&cs[i] == cs[i-1] && !flg[i-1]) {
                //和前面元素相同 且  没使用过
                continue;
            }

            str1.append(cs[i]);
            //用过了  标记一下
            flg[i] = true;
            //继续下一个
            dfs(index+1);
            //恢复
            flg[i]  = false;
            //把记录的那个给删了
            str1.deleteCharAt(str1.length()-1);
        }
    }
}
